//给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。 
//
// 请你找出符合题意的 最短 子数组，并输出它的长度。 
//
// 
//
// 
// 
// 示例 1： 
//
// 
//输入：nums = [2,6,4,8,10,9,15]
//输出：5
//解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
// 
//
// 示例 2： 
//
// 
//输入：nums = [1,2,3,4]
//输出：0
// 
//
// 示例 3： 
//
// 
//输入：nums = [1]
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 104 
// -105 <= nums[i] <= 105 
// 
//
// 
//
// 进阶：你可以设计一个时间复杂度为 O(n) 的解决方案吗？ 
// 
// 
// Related Topics 栈 贪心 数组 双指针 排序 单调栈 
// 👍 710 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
func findUnsortedSubarray(nums []int) int {

    // tips:
    // 解法1： copy nums 排序 比对 前后双指针比对

//     numsSort := make([]int, len(nums))
//     copy(numsSort, nums)
//     sort.Ints(numsSort)
//
//     left, right := 0, len(nums) - 1 // 左右指针
//
//     for left <= right && numsSort[left] == nums[left] {
//         left++
//     }
//
//     for left <= right && numsSort[right] == nums[right] {
//         right--
//     }
//
//     return right - left + 1

    // 解法2：
    // 前后双指针
    // 用左侧最大值确认右侧边界, 用右侧最小值确认左侧边界
    // 右侧边界一定比左侧最大值要小, 左侧边界一定比右侧最小值要大

    if len(nums) <= 1 {
        return 0
    }

    leftMax, rightMin := nums[0], nums[len(nums) - 1]

    left, right := 0, -1 // 待排序的左右边界  为了最后输出值+1 初始值定位-1

    for i := 0; i < len(nums); i++ {
        if leftMax > nums[i] {
            right = i
        } else {
            leftMax = nums[i]
        }

        if rightMin < nums[len(nums) - i - 1] {
            left = len(nums) - i - 1
        } else {
            rightMin = nums[len(nums) - i - 1]
        }
    }

    return right - left  + 1
}
//leetcode submit region end(Prohibit modification and deletion)
